//You are given two integer arrays nums1 and nums2 both of unique elements, wher
//e nums1 is a subset of nums2.
//
// Find all the next greater numbers for nums1's elements in the corresponding p
//laces of nums2.
//
// The Next Greater Number of a number x in nums1 is the first greater number to
// its right in nums2. If it does not exist, return -1 for this number.
//
//
// Example 1:
//
//
//Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
//Output: [-1,3,-1]
//Explanation:
//For number 4 in the first array, you cannot find the next greater number for i
//t in the second array, so output -1.
//For number 1 in the first array, the next greater number for it in the second
//array is 3.
//For number 2 in the first array, there is no next greater number for it in the
// second array, so output -1.
//
// Example 2:
//
//
//Input: nums1 = [2,4], nums2 = [1,2,3,4]
//Output: [3,-1]
//Explanation:
//For number 2 in the first array, the next greater number for it in the second
//array is 3.
//For number 4 in the first array, there is no next greater number for it in the
// second array, so output -1.
//
//
// Constraints:
//
//
// 1 <= nums1.length <= nums2.length <= 1000
// 0 <= nums1[i], nums2[i] <= 104
// All integers in nums1 and nums2 are unique.
// All the integers of nums1 also appear in nums2.
//
//
//
//Follow up: Could you find an O(nums1.length + nums2.length) solution? Related
//Topics 栈
// 👍 415 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Next Greater Element I
class P496NextGreaterElementI {
    public static void main(String[] args) {
        Solution solution = new P496NextGreaterElementI().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int[] arr = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++) {
                int index = -1;
                out:
                for (int j = 0; j < nums2.length; j++) {
                    if (nums2[j] == nums1[i]) {
                        for (int k = j + 1; k < nums2.length; k++) {
                            if (nums2[k] > nums1[i]) {
                                index = k;
                                break out;
                            }
                        }
                    }
                }
                arr[i] = index == -1 ? -1 : nums2[index];
            }
            return arr;
        }

        public int[] nextGreaterElementStack(int[] nums1, int[] nums2) {
            int[] arr = new int[nums1.length];
            // 存大的数
            Map<Integer, Integer> greaterMap = new HashMap<>();
            int index = 0;
            Stack<Integer> stack = new Stack<>();
            for (int i = nums2.length - 1; i >= 0; i--) {
                int ele = nums2[i];
                while (!stack.isEmpty() && ele > stack.peek()) {
                    stack.pop();
                }
                greaterMap.put(ele, stack.isEmpty() ? -1 : stack.peek());
                stack.add(ele);
            }
            for (int i = 0; i < nums1.length; i++) {
                int ele = nums1[i];
                if (greaterMap.containsKey(ele)) {
                    arr[i] = Optional.ofNullable(greaterMap.get(ele)).orElse(-1);
                }else{
                    arr[i] = -1;
                }
            }
            return arr;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)
}
